<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>树与图-cnblog | 凌歆的博客</title>
    <meta name="generator" content="VuePress 1.9.5">
    <link rel="icon" href="/img/favicon.ico">
    <meta name="description" content="web前端技术博客,专注web前端学习与总结。JavaScript,js,ES6,TypeScript,vue,React,python,css3,html5,Node,git,github等技术文章。">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,markdown">
    <meta name="baidu-site-verification" content="7F55weZDDc">
    <meta name="theme-color" content="#11a8cd">
    
    <link rel="preload" href="/assets/css/0.styles.d9c8cf8c.css" as="style"><link rel="preload" href="/assets/js/app.57550e13.js" as="script"><link rel="preload" href="/assets/js/2.f014c35f.js" as="script"><link rel="preload" href="/assets/js/107.a81b32d7.js" as="script"><link rel="prefetch" href="/assets/js/10.03a98811.js"><link rel="prefetch" href="/assets/js/100.145e708e.js"><link rel="prefetch" href="/assets/js/101.098ca5c8.js"><link rel="prefetch" href="/assets/js/102.4d45c69a.js"><link rel="prefetch" href="/assets/js/103.499de505.js"><link rel="prefetch" href="/assets/js/104.c2c1b9b6.js"><link rel="prefetch" href="/assets/js/105.4e9b0663.js"><link rel="prefetch" href="/assets/js/106.9bb8cf6f.js"><link rel="prefetch" href="/assets/js/108.81511e67.js"><link rel="prefetch" href="/assets/js/109.6a6741bf.js"><link rel="prefetch" href="/assets/js/11.e8729182.js"><link rel="prefetch" href="/assets/js/110.de657fe7.js"><link rel="prefetch" href="/assets/js/111.b092af6d.js"><link rel="prefetch" href="/assets/js/112.2dca5709.js"><link rel="prefetch" href="/assets/js/113.dbed1fac.js"><link rel="prefetch" href="/assets/js/114.e95a0131.js"><link rel="prefetch" href="/assets/js/115.2e3e8285.js"><link rel="prefetch" href="/assets/js/116.e64f7fec.js"><link rel="prefetch" href="/assets/js/117.583552c9.js"><link rel="prefetch" href="/assets/js/118.aa5d18f0.js"><link rel="prefetch" href="/assets/js/119.0c7b52d7.js"><link rel="prefetch" href="/assets/js/12.d63acec2.js"><link rel="prefetch" href="/assets/js/120.13f86281.js"><link rel="prefetch" href="/assets/js/121.e2b5b7f9.js"><link rel="prefetch" href="/assets/js/122.5252216a.js"><link rel="prefetch" href="/assets/js/123.8b8a3503.js"><link rel="prefetch" href="/assets/js/124.60df855c.js"><link rel="prefetch" href="/assets/js/125.f073ab1c.js"><link rel="prefetch" href="/assets/js/126.7b73de6a.js"><link rel="prefetch" href="/assets/js/127.4e25971c.js"><link rel="prefetch" href="/assets/js/128.0edf0e06.js"><link rel="prefetch" href="/assets/js/129.5cb5a70a.js"><link rel="prefetch" href="/assets/js/13.2259ef71.js"><link rel="prefetch" href="/assets/js/130.00247fda.js"><link rel="prefetch" href="/assets/js/131.d6fc003a.js"><link rel="prefetch" href="/assets/js/132.1a32b18f.js"><link rel="prefetch" href="/assets/js/133.e46c0193.js"><link rel="prefetch" href="/assets/js/134.a6ad681f.js"><link rel="prefetch" href="/assets/js/135.2fcbe137.js"><link rel="prefetch" href="/assets/js/136.f69bf451.js"><link rel="prefetch" href="/assets/js/137.b9ef2fcc.js"><link rel="prefetch" href="/assets/js/138.7fdd9feb.js"><link rel="prefetch" href="/assets/js/139.a3a37c91.js"><link rel="prefetch" href="/assets/js/14.0d6b23b9.js"><link rel="prefetch" href="/assets/js/140.a7c013ae.js"><link rel="prefetch" href="/assets/js/141.956c36ce.js"><link rel="prefetch" href="/assets/js/142.5aacfe42.js"><link rel="prefetch" href="/assets/js/143.57d691ef.js"><link rel="prefetch" href="/assets/js/144.b1e5766e.js"><link rel="prefetch" href="/assets/js/145.463284b7.js"><link rel="prefetch" href="/assets/js/146.6cc6420c.js"><link rel="prefetch" href="/assets/js/147.5b78c5a2.js"><link rel="prefetch" href="/assets/js/148.8d1d7679.js"><link rel="prefetch" href="/assets/js/149.4e0eb213.js"><link rel="prefetch" href="/assets/js/15.f6fde69d.js"><link rel="prefetch" href="/assets/js/150.b183de37.js"><link rel="prefetch" href="/assets/js/151.729ae770.js"><link rel="prefetch" href="/assets/js/152.b1297018.js"><link rel="prefetch" href="/assets/js/153.bb991bca.js"><link rel="prefetch" href="/assets/js/154.6f2286aa.js"><link rel="prefetch" href="/assets/js/155.6a9c7e4d.js"><link rel="prefetch" href="/assets/js/156.f7bd535d.js"><link rel="prefetch" href="/assets/js/157.64c0065c.js"><link rel="prefetch" href="/assets/js/158.d31ae949.js"><link rel="prefetch" href="/assets/js/159.7daea8a7.js"><link rel="prefetch" href="/assets/js/16.7be21beb.js"><link rel="prefetch" href="/assets/js/160.33cc971a.js"><link rel="prefetch" href="/assets/js/161.1676442a.js"><link rel="prefetch" href="/assets/js/162.71378046.js"><link rel="prefetch" href="/assets/js/163.99e49959.js"><link rel="prefetch" href="/assets/js/164.306f07d2.js"><link rel="prefetch" href="/assets/js/165.170977c7.js"><link rel="prefetch" href="/assets/js/166.f8602525.js"><link rel="prefetch" href="/assets/js/167.eea5c001.js"><link rel="prefetch" href="/assets/js/168.0146a311.js"><link rel="prefetch" href="/assets/js/169.05f9c9d9.js"><link rel="prefetch" href="/assets/js/17.2543f471.js"><link rel="prefetch" href="/assets/js/170.25d602b2.js"><link rel="prefetch" href="/assets/js/171.1ada26a6.js"><link rel="prefetch" href="/assets/js/172.2a0f697c.js"><link rel="prefetch" href="/assets/js/173.230d8ca8.js"><link rel="prefetch" href="/assets/js/174.e3758a2b.js"><link rel="prefetch" href="/assets/js/175.0f19f8ea.js"><link rel="prefetch" href="/assets/js/176.bf70d37d.js"><link rel="prefetch" href="/assets/js/177.4400f272.js"><link rel="prefetch" href="/assets/js/178.85af7b89.js"><link rel="prefetch" href="/assets/js/179.4cfaaaa2.js"><link rel="prefetch" href="/assets/js/18.394415f8.js"><link rel="prefetch" href="/assets/js/180.449c8409.js"><link rel="prefetch" href="/assets/js/181.73276924.js"><link rel="prefetch" href="/assets/js/182.5fab25cc.js"><link rel="prefetch" href="/assets/js/183.ecd4934d.js"><link rel="prefetch" href="/assets/js/184.246092cf.js"><link rel="prefetch" href="/assets/js/185.c671cd86.js"><link rel="prefetch" href="/assets/js/186.49bd1963.js"><link rel="prefetch" href="/assets/js/187.1fb32764.js"><link rel="prefetch" href="/assets/js/188.7c6885e9.js"><link rel="prefetch" href="/assets/js/189.a8701dec.js"><link rel="prefetch" href="/assets/js/19.ca7db8ea.js"><link rel="prefetch" href="/assets/js/190.ae3d3bde.js"><link rel="prefetch" href="/assets/js/191.ad7cd44e.js"><link rel="prefetch" href="/assets/js/192.bc443842.js"><link rel="prefetch" href="/assets/js/193.e4755764.js"><link rel="prefetch" href="/assets/js/194.814112ce.js"><link rel="prefetch" href="/assets/js/195.1c0aaa80.js"><link rel="prefetch" href="/assets/js/196.a6bd7add.js"><link rel="prefetch" href="/assets/js/20.4e91cd31.js"><link rel="prefetch" href="/assets/js/21.f095e6e1.js"><link rel="prefetch" href="/assets/js/22.72f4b8ab.js"><link rel="prefetch" href="/assets/js/23.e94eb9d2.js"><link rel="prefetch" href="/assets/js/24.0eae7d6f.js"><link rel="prefetch" href="/assets/js/25.36157609.js"><link rel="prefetch" href="/assets/js/26.dc5b6cba.js"><link rel="prefetch" href="/assets/js/27.c19b7b63.js"><link rel="prefetch" href="/assets/js/28.3aceae59.js"><link rel="prefetch" href="/assets/js/29.536091b3.js"><link rel="prefetch" href="/assets/js/3.d11119c4.js"><link rel="prefetch" href="/assets/js/30.821a4a30.js"><link rel="prefetch" href="/assets/js/31.5238784c.js"><link rel="prefetch" href="/assets/js/32.10bc7179.js"><link rel="prefetch" href="/assets/js/33.c1ed69c9.js"><link rel="prefetch" href="/assets/js/34.8d384231.js"><link rel="prefetch" href="/assets/js/35.d8890e52.js"><link rel="prefetch" href="/assets/js/36.eca37ad5.js"><link rel="prefetch" href="/assets/js/37.802549e3.js"><link rel="prefetch" href="/assets/js/38.53841770.js"><link rel="prefetch" href="/assets/js/39.7ae44409.js"><link rel="prefetch" href="/assets/js/4.493b9bca.js"><link rel="prefetch" href="/assets/js/40.ce56364a.js"><link rel="prefetch" href="/assets/js/41.85f0114b.js"><link rel="prefetch" href="/assets/js/42.714da6e2.js"><link rel="prefetch" href="/assets/js/43.fee4437c.js"><link rel="prefetch" href="/assets/js/44.b039b68b.js"><link rel="prefetch" href="/assets/js/45.96a55605.js"><link rel="prefetch" href="/assets/js/46.956ffb03.js"><link rel="prefetch" href="/assets/js/47.147d9218.js"><link rel="prefetch" href="/assets/js/48.ff787b40.js"><link rel="prefetch" href="/assets/js/49.871eee87.js"><link rel="prefetch" href="/assets/js/5.e0ba07d7.js"><link rel="prefetch" href="/assets/js/50.99b7c29e.js"><link rel="prefetch" href="/assets/js/51.8ecbf4ba.js"><link rel="prefetch" href="/assets/js/52.53d91d7e.js"><link rel="prefetch" href="/assets/js/53.af8a0d2a.js"><link rel="prefetch" href="/assets/js/54.a2f848b5.js"><link rel="prefetch" href="/assets/js/55.267e9947.js"><link rel="prefetch" href="/assets/js/56.0b201c40.js"><link rel="prefetch" href="/assets/js/57.cbdfd6f7.js"><link rel="prefetch" href="/assets/js/58.636c0c3f.js"><link rel="prefetch" href="/assets/js/59.fc9216c4.js"><link rel="prefetch" href="/assets/js/6.b98373f2.js"><link rel="prefetch" href="/assets/js/60.34f16fc4.js"><link rel="prefetch" href="/assets/js/61.4d130bd8.js"><link rel="prefetch" href="/assets/js/62.927caa10.js"><link rel="prefetch" href="/assets/js/63.a451fee0.js"><link rel="prefetch" href="/assets/js/64.32a5d47b.js"><link rel="prefetch" href="/assets/js/65.bc099429.js"><link rel="prefetch" href="/assets/js/66.3953050d.js"><link rel="prefetch" href="/assets/js/67.e934823b.js"><link rel="prefetch" href="/assets/js/68.4bcb52b0.js"><link rel="prefetch" href="/assets/js/69.bede18c8.js"><link rel="prefetch" href="/assets/js/7.8de8df2d.js"><link rel="prefetch" href="/assets/js/70.fce1daac.js"><link rel="prefetch" href="/assets/js/71.ea0a8c5d.js"><link rel="prefetch" href="/assets/js/72.15382c9e.js"><link rel="prefetch" href="/assets/js/73.848364d3.js"><link rel="prefetch" href="/assets/js/74.5fd08a50.js"><link rel="prefetch" href="/assets/js/75.c937c70d.js"><link rel="prefetch" href="/assets/js/76.a0dacd5a.js"><link rel="prefetch" href="/assets/js/77.4019cc23.js"><link rel="prefetch" href="/assets/js/78.9676a9e1.js"><link rel="prefetch" href="/assets/js/79.e46e10d5.js"><link rel="prefetch" href="/assets/js/8.2098eb96.js"><link rel="prefetch" href="/assets/js/80.987e83cb.js"><link rel="prefetch" href="/assets/js/81.eb98ff36.js"><link rel="prefetch" href="/assets/js/82.623561a7.js"><link rel="prefetch" href="/assets/js/83.e256d909.js"><link rel="prefetch" href="/assets/js/84.7d06a550.js"><link rel="prefetch" href="/assets/js/85.b8d9879e.js"><link rel="prefetch" href="/assets/js/86.31c4581b.js"><link rel="prefetch" href="/assets/js/87.e06ee05e.js"><link rel="prefetch" href="/assets/js/88.81ef718d.js"><link rel="prefetch" href="/assets/js/89.ba237d2f.js"><link rel="prefetch" href="/assets/js/9.36092fd0.js"><link rel="prefetch" href="/assets/js/90.ad2c9d92.js"><link rel="prefetch" href="/assets/js/91.a661f52d.js"><link rel="prefetch" href="/assets/js/92.1c28035b.js"><link rel="prefetch" href="/assets/js/93.c8b8e3d6.js"><link rel="prefetch" href="/assets/js/94.b6bc4a44.js"><link rel="prefetch" href="/assets/js/95.92cea882.js"><link rel="prefetch" href="/assets/js/96.5373491b.js"><link rel="prefetch" href="/assets/js/97.bb39efc8.js"><link rel="prefetch" href="/assets/js/98.af7a030f.js"><link rel="prefetch" href="/assets/js/99.07dc87d8.js">
    <link rel="stylesheet" href="/assets/css/0.styles.d9c8cf8c.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png" alt="凌歆的博客" class="logo"> <span class="site-name can-hide">凌歆的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png"> <div class="blogger-info"><h3>lingxin</h3> <span>凌歆</span></div></div> <nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>学习笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法训练营</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/8ebdeb/" class="sidebar-link">数组-链表-栈-队列-cnblog</a></li><li><a href="/pages/8585b9/" class="sidebar-link">数组-链表-栈-队列（下）-cnblog</a></li><li><a href="/pages/1848ee/" class="sidebar-link">哈希表-集合-映射-cnblog</a></li><li><a href="/pages/32c8c0/" class="sidebar-link">前缀和-差分-双指针（上）-cnblog</a></li><li><a href="/pages/9b8692/" class="sidebar-link">前缀和-差分-双指针（下）-cnblog</a></li><li><a href="/pages/7f3ede/" class="sidebar-link">算法训练营-排序-cnblog</a></li><li><a href="/pages/cbca68/" class="sidebar-link">二分</a></li><li><a href="/pages/1a456e/" class="sidebar-link">三分-二分答案</a></li><li><a href="/pages/3fd3d8/" aria-current="page" class="active sidebar-link">树与图-cnblog</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/pages/7c3255/" class="sidebar-link">二叉搜索树</a></li><li><a href="/pages/cf81aa/" class="sidebar-link">二叉堆</a></li><li><a href="/pages/1cde21/" class="sidebar-link">递归-分治</a></li><li><a href="/pages/0e21af/" class="sidebar-link">深度-广度搜索-状态空间-cnblog</a></li><li><a href="/pages/6789f3/" class="sidebar-link">动态规划(一)</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>js数据结构与算法</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"><div class="theme-vdoing-wrapper "><div class="articleInfo-wrap" data-v-06225672><div class="articleInfo" data-v-06225672><ul class="breadcrumbs" data-v-06225672><li data-v-06225672><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-06225672></a></li> <li data-v-06225672><a href="/algor/#算法" data-v-06225672>算法</a></li><li data-v-06225672><a href="/algor/#算法训练营" data-v-06225672>算法训练营</a></li></ul> <div class="info" data-v-06225672><div title="作者" class="author iconfont icon-touxiang" data-v-06225672><a href="https://github.com/linxin1123" target="_blank" title="作者" class="beLink" data-v-06225672>lingxin</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-06225672><a href="javascript:;" data-v-06225672>2023-02-17</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-title">目录</div> <div class="right-menu-content"></div></div></div> <h1><img src="">树与图-cnblog<!----></h1>  <div class="theme-vdoing-content content__default"><h4 id="_589-n-叉树的前序遍历"><a href="#_589-n-叉树的前序遍历" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/n-ary-tree-preorder-traversal/description/" target="_blank" rel="noopener noreferrer">589. N 叉树的前序遍历<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个 n 叉树的根节点 <code>root</code> ，返回 <em>其节点值的 <strong>前序遍历</strong></em> 。</p> <p>n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 <code>null</code> 分隔（请参见示例）。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li>节点总数在范围 <code>[0, 104]</code>内</li> <li><code>0 &lt;= Node.val &lt;= 104</code></li> <li>n 叉树的高度小于或等于 <code>1000</code></li></ul> <h5 id="解题思路"><a href="#解题思路" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 变量，前序<span class="token operator">==</span><span class="token operator">&gt;</span>深度优先搜索
<span class="token number">2</span>. n叉树<span class="token operator">=</span><span class="token operator">&gt;</span>遍历根，遍历所有孩子节点
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="递归"><a href="#递归" class="header-anchor">#</a> 递归</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code> <span class="token keyword">const</span> <span class="token function-variable function">preOrder</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
         <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>root<span class="token punctuation">)</span><span class="token punctuation">{</span>
             <span class="token keyword">return</span> 
         <span class="token punctuation">}</span>
    
         <span class="token comment">// console.log(root.val)</span>
         res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>val<span class="token punctuation">)</span>

         <span class="token comment">// console.log(root.children)</span>
         <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>root<span class="token punctuation">.</span>children<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token function">preOrder</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>children<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
         <span class="token punctuation">}</span>
     <span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br></div></div><h5 id="迭代"><a href="#迭代" class="header-anchor">#</a> 迭代</h5> <ul><li><p>关键在于使用栈来模拟递归的堆栈调用</p></li> <li><p><img src="https://img2023.cnblogs.com/blog/3089561/202302/3089561-20230203130656304-646417754.jpg" alt=""></p></li></ul> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */</span>

<span class="token comment">/**
 * @param {Node|null} root
 * @return {number[]}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">preorder</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 迭代的方法实现</span>

    <span class="token comment">// 关键在于使用栈来模拟递归调用堆栈</span>

    <span class="token comment">// const preOrder=(root)=&gt;{</span>
    <span class="token comment">//     if(!root){</span>
    <span class="token comment">//         return </span>
    <span class="token comment">//     }</span>
    
    <span class="token comment">//     // console.log(root.val)</span>
    <span class="token comment">//     res.push(root.val)</span>

    <span class="token comment">//     // console.log(root.children)</span>
    <span class="token comment">//     for(let i=0;i&lt;root.children.length;i++){</span>
    <span class="token comment">//         preOrder(root.children[i])</span>
    <span class="token comment">//     }</span>
    <span class="token comment">// }</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> stack<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>root<span class="token punctuation">)</span>
    
    <span class="token keyword">while</span><span class="token punctuation">(</span>stack<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>
        
        <span class="token keyword">let</span> node<span class="token operator">=</span>stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token keyword">break</span>
        res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span>node<span class="token punctuation">.</span>children<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&gt;=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>children<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    


    <span class="token keyword">return</span> res
    
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br></div></div><h4 id="_429-n-叉树的层序遍历"><a href="#_429-n-叉树的层序遍历" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/" target="_blank" rel="noopener noreferrer">429. N 叉树的层序遍历<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个 N 叉树，返回其节点值的<em>层序遍历</em>。（即从左到右，逐层遍历）。</p> <p>树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li>树的高度不会超过 <code>1000</code></li> <li>树的节点总数在 <code>[0, 10^4]</code> 之间</li></ul> <h5 id="解题思路-2"><a href="#解题思路-2" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 层序遍历，一般需要使用队列维护
<span class="token number">2</span>. 结果集分组，需要为队列中的每个元素添加深度
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="完整代码"><a href="#完整代码" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */</span>

<span class="token comment">/**
 * @param {Node|null} root
 * @return {number[][]}
 */</span>

 <span class="token keyword">function</span> <span class="token function">NodeWithLevel</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span>level</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

     <span class="token keyword">this</span><span class="token punctuation">.</span>node<span class="token operator">=</span>node
     <span class="token keyword">this</span><span class="token punctuation">.</span>level<span class="token operator">=</span>level

 <span class="token punctuation">}</span>
<span class="token keyword">var</span> <span class="token function-variable function">levelOrder</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    
    <span class="token comment">// 层序遍历，一般都是使用一个队列来维护</span>
    <span class="token keyword">let</span> queue<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> levelNode<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">NodeWithLevel</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">)</span>
    queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">)</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> levelNode<span class="token operator">=</span>queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">)</span> <span class="token keyword">break</span>

        <span class="token comment">// 结果集合</span>
        <span class="token keyword">let</span> level<span class="token operator">=</span>levelNode<span class="token punctuation">.</span>level<span class="token operator">-</span><span class="token number">1</span>
        <span class="token comment">// res[level]=res[level]===undefined? []:res[level].push(levelNode.node.val) </span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
            res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
            res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 孩子节点入队</span>
        
        <span class="token keyword">let</span> length<span class="token operator">=</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>children<span class="token punctuation">.</span>length

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> aNode<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">NodeWithLevel</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>children<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>levelNode<span class="token punctuation">.</span>level<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>aNode<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>


    <span class="token keyword">return</span> res


<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br></div></div><h4 id="_297-二叉树的序列化与反序列化"><a href="#_297-二叉树的序列化与反序列化" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/" target="_blank" rel="noopener noreferrer">297. 二叉树的序列化与反序列化<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。</p> <p>请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。</p> <p><strong>提示:</strong> 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 <a href="https://leetcode.cn/faq/#binary-tree" target="_blank" rel="noopener noreferrer">LeetCode 序列化二叉树的格式<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = []
输出：[]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1]
输出：[1]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 4：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,2]
输出：[1,2]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li>树中结点数在范围 <code>[0, 104]</code> 内</li> <li><code>-1000 &lt;= Node.val &lt;= 1000</code></li></ul> <h5 id="解题思路-3"><a href="#解题思路-3" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 序列化和反序列化其实就是树结构和字符串的转化
<span class="token number">2</span>. 序列化将树结构转化为前序字符串
<span class="token number">3</span>. 反序列化将前序字符串转化为树结构
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h5 id="完整代码-2"><a href="#完整代码-2" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */</span>

<span class="token comment">/**
 * @param {Node|null} root
 * @return {number[][]}
 */</span>

 <span class="token keyword">function</span> <span class="token function">NodeWithLevel</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span>level</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

     <span class="token keyword">this</span><span class="token punctuation">.</span>node<span class="token operator">=</span>node
     <span class="token keyword">this</span><span class="token punctuation">.</span>level<span class="token operator">=</span>level

 <span class="token punctuation">}</span>
<span class="token keyword">var</span> <span class="token function-variable function">levelOrder</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    
    <span class="token comment">// 层序遍历，一般都是使用一个队列来维护</span>
    <span class="token keyword">let</span> queue<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> levelNode<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">NodeWithLevel</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">)</span>
    queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">)</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> levelNode<span class="token operator">=</span>queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">)</span> <span class="token keyword">break</span>

        <span class="token comment">// 结果集合</span>
        <span class="token keyword">let</span> level<span class="token operator">=</span>levelNode<span class="token punctuation">.</span>level<span class="token operator">-</span><span class="token number">1</span>
        <span class="token comment">// res[level]=res[level]===undefined? []:res[level].push(levelNode.node.val) </span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
            res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
            res<span class="token punctuation">[</span>level<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 孩子节点入队</span>
        
        <span class="token keyword">let</span> length<span class="token operator">=</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>children<span class="token punctuation">.</span>length

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> aNode<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">NodeWithLevel</span><span class="token punctuation">(</span>levelNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>children<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>levelNode<span class="token punctuation">.</span>level<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>aNode<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>


    <span class="token keyword">return</span> res


<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br></div></div><h4 id="_105-从前序与中序遍历序列构造二叉树"><a href="#_105-从前序与中序遍历序列构造二叉树" class="header-anchor">#</a> 105. <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/" target="_blank" rel="noopener noreferrer">从前序与中序遍历序列构造二叉树<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定两个整数数组 <code>preorder</code> 和 <code>inorder</code> ，其中 <code>preorder</code> 是二叉树的<strong>先序遍历</strong>， <code>inorder</code> 是同一棵树的<strong>中序遍历</strong>，请构造二叉树并返回其根节点。</p> <p><strong>示例 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/02/19/tree.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: preorder = [-1], inorder = [-1]
输出: [-1]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示:</strong></p> <ul><li><code>1 &lt;= preorder.length &lt;= 3000</code></li> <li><code>inorder.length == preorder.length</code></li> <li><code>-3000 &lt;= preorder[i], inorder[i] &lt;= 3000</code></li> <li><code>preorder</code> 和 <code>inorder</code> 均 <strong>无重复</strong> 元素</li> <li><code>inorder</code> 均出现在 <code>preorder</code></li> <li><code>preorder</code> <strong>保证</strong> 为二叉树的前序遍历序列</li> <li><code>inorder</code> <strong>保证</strong> 为二叉树的中序遍历序列</li></ul> <h5 id="解题思路-4"><a href="#解题思路-4" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 前序序列告诉我们根的值
<span class="token number">2</span>. 中序遍历告诉我们根的位置
<span class="token number">3</span>. 降规模
	原树划分为左子树和右子树
	重复1，2操作
	
<span class="token number">4</span>. 递归出口，前序序列的范围不合法
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><h5 id="完整代码-3"><a href="#完整代码-3" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */</span>
<span class="token comment">/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">buildTree</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">preorder<span class="token punctuation">,</span> inorder</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 我们把问题进行分解降规模</span>

    <span class="token comment">// 对于[3,9,20,15,7]</span>
    <span class="token comment">// 前序遍历告诉我们root=3</span>
    <span class="token comment">// 中序遍历[9,3,15,20,7] 告诉我们3的位置</span>

    <span class="token comment">// 问题分解为</span>

    <span class="token punctuation">[</span><span class="token number">9</span> <span class="token operator">|</span> <span class="token number">3</span> <span class="token operator">|</span> <span class="token number">15</span><span class="token punctuation">,</span><span class="token number">20</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">]</span>

    <span class="token comment">// 左子树[9]</span>
    <span class="token comment">// 右子树 [15,20,7]</span>

    <span class="token comment">// 对左右子树递归分解问题</span>

    

    <span class="token comment">// 递归子问题</span>
    <span class="token keyword">const</span> <span class="token function-variable function">build</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">l1<span class="token punctuation">,</span>r1<span class="token punctuation">,</span>l2<span class="token punctuation">,</span>r2</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>

        <span class="token comment">// l1 r1 确定前序序列的范围</span>

        <span class="token comment">// l2,r2 确定中序序列的范围</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>l1<span class="token operator">&gt;</span>r1<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">null</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 确定根</span>
        <span class="token keyword">let</span> root <span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">TreeNode</span><span class="token punctuation">(</span>preorder<span class="token punctuation">[</span>l1<span class="token punctuation">]</span><span class="token punctuation">)</span>

        

        <span class="token comment">// 确定分界点</span>
        <span class="token comment">// 从中序序列找，找到根</span>
        <span class="token keyword">let</span> point<span class="token operator">=</span>l2
        <span class="token keyword">while</span><span class="token punctuation">(</span>inorder<span class="token punctuation">[</span>point<span class="token punctuation">]</span><span class="token operator">!==</span>preorder<span class="token punctuation">[</span>l1<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            point<span class="token operator">++</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 确定左子树和右子树</span>

        <span class="token keyword">let</span> leftSize<span class="token operator">=</span>point<span class="token operator">-</span>l2
        <span class="token comment">// let rightSize=r2-point</span>



        root<span class="token punctuation">.</span>left<span class="token operator">=</span><span class="token function">build</span><span class="token punctuation">(</span>l1<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>l1<span class="token operator">+</span>leftSize<span class="token punctuation">,</span>l2<span class="token punctuation">,</span>point<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
        root<span class="token punctuation">.</span>right<span class="token operator">=</span><span class="token function">build</span><span class="token punctuation">(</span>l1<span class="token operator">+</span>leftSize<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r1<span class="token punctuation">,</span>point<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r2<span class="token punctuation">)</span>

        <span class="token keyword">return</span> root
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> <span class="token function">build</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span>preorder<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>inorder<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>


<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br></div></div><h4 id="_236-二叉树的最近公共祖先"><a href="#_236-二叉树的最近公共祖先" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/" target="_blank" rel="noopener noreferrer">236. 二叉树的最近公共祖先<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。</p> <p><a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin" target="_blank" rel="noopener noreferrer">百度百科<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（<strong>一个节点也可以是它自己的祖先</strong>）。”</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：root = [1,2], p = 1, q = 2
输出：1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li>树中节点数目在范围 <code>[2, 105]</code> 内。</li> <li><code>-109 &lt;= Node.val &lt;= 109</code></li> <li>所有 <code>Node.val</code> <code>互不相同</code> 。</li> <li><code>p != q</code></li> <li><code>p</code> 和 <code>q</code> 均存在于给定的二叉树中。</li></ul> <h5 id="解题思路-5"><a href="#解题思路-5" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 暴力
	把每个节点遍历一次，同时存储每个节点的父节点和深度
	遍历过程找到p,q节点
	根据找出的 p,q 节点通过存储的父节点找到祖先
	
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><ul><li>优化版本</li></ul> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 思路还是暴力，但在空间和时间复杂度上有优化
	我们只存储每个节点的父节点和一个激化标记（默认false）
	q节点往上走到根，走过的激化<span class="token punctuation">(</span>包含自身<span class="token punctuation">)</span>标记为true
	p节点往上走，遇到激活标记结束，找到了共同祖先
	
	
	其实空间复杂度差不多，时间上有优化，不需要每次比较值，只需要看激活标记即可
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><ul><li>心得体会</li></ul> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 把原节点变为包含额外父节点的节点 ，可以定义一个数据结构，将原数据结构node进行改造，但是空间有浪费

<span class="token number">2</span>. 其实应该这样 <span class="token keyword">function</span> MyNode<span class="token punctuation">(</span>val,node<span class="token punctuation">)</span><span class="token punctuation">{</span>
	<span class="token assign-left variable">this.val</span><span class="token operator">=</span>val
	<span class="token assign-left variable">this.parentNode</span><span class="token operator">=</span>node
<span class="token punctuation">}</span>

<span class="token number">3</span>. 或者使用map

<span class="token builtin class-name">let</span> <span class="token assign-left variable">m</span><span class="token operator">=</span>new Map<span class="token punctuation">(</span><span class="token punctuation">)</span>
m.set<span class="token punctuation">(</span>p.val,p.parentNode<span class="token punctuation">)</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br></div></div><h5 id="完整代码-4"><a href="#完整代码-4" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */</span>
<span class="token comment">/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */</span>

 <span class="token keyword">function</span> <span class="token function">MyNode</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span>parentNode<span class="token punctuation">,</span>depth</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

     <span class="token keyword">this</span><span class="token punctuation">.</span>node<span class="token operator">=</span>node
     <span class="token keyword">this</span><span class="token punctuation">.</span>parentNode<span class="token operator">=</span>parentNode
     <span class="token keyword">this</span><span class="token punctuation">.</span>depth<span class="token operator">=</span>depth
 <span class="token punctuation">}</span>
<span class="token keyword">var</span> <span class="token function-variable function">lowestCommonAncestor</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">root<span class="token punctuation">,</span> p<span class="token punctuation">,</span> q</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 1.  暴力</span>
    
    <span class="token comment">// 将这棵树遍历一次，每个节点存储它的父节点和该节点对应的层数</span>

    <span class="token comment">// 这里使用广度优先遍历</span>

    <span class="token keyword">let</span> queue<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> myNodeList<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> myRoot<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">MyNode</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span><span class="token keyword">null</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span>


    queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>myRoot<span class="token punctuation">)</span>
    myNodeList<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>myRoot<span class="token punctuation">)</span>

    <span class="token keyword">let</span> pNode<span class="token punctuation">;</span>
    <span class="token keyword">let</span> qNode<span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> curNode<span class="token operator">=</span>queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>curNode<span class="token punctuation">.</span>node<span class="token punctuation">)</span> <span class="token keyword">break</span>

        <span class="token comment">// console.log(curNode.node.val)</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>curNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token operator">===</span>p<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">{</span>
            console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>
            pNode<span class="token operator">=</span>curNode
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>curNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token operator">===</span>q<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">{</span>
            qNode<span class="token operator">=</span>curNode
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> leftNode<span class="token operator">=</span>curNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>left
        <span class="token keyword">let</span> rightNode<span class="token operator">=</span>curNode<span class="token punctuation">.</span>node<span class="token punctuation">.</span>right

        <span class="token keyword">if</span><span class="token punctuation">(</span>leftNode<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> myLeftNode<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">MyNode</span><span class="token punctuation">(</span>leftNode<span class="token punctuation">,</span>curNode<span class="token punctuation">,</span>curNode<span class="token punctuation">.</span>depth<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>myLeftNode<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>rightNode<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> myRightNode<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">MyNode</span><span class="token punctuation">(</span>rightNode<span class="token punctuation">,</span>curNode<span class="token punctuation">,</span>curNode<span class="token punctuation">.</span>depth<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>myRightNode<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>pNode<span class="token punctuation">)</span>
    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>qNode<span class="token punctuation">)</span>

    <span class="token comment">// 开始寻找祖先</span>

    <span class="token comment">// 我们先让p，q节点层级相同</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>pNode<span class="token punctuation">.</span>depth<span class="token operator">&gt;</span>qNode<span class="token punctuation">.</span>depth<span class="token punctuation">)</span><span class="token punctuation">{</span>
        pNode<span class="token operator">=</span>pNode<span class="token punctuation">.</span>parentNode
    <span class="token punctuation">}</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>qNode<span class="token punctuation">.</span>depth<span class="token operator">&gt;</span>pNode<span class="token punctuation">.</span>depth<span class="token punctuation">)</span><span class="token punctuation">{</span>
        qNode<span class="token operator">=</span>qNode<span class="token punctuation">.</span>parentNode
    <span class="token punctuation">}</span>

    <span class="token keyword">const</span> <span class="token function-variable function">getParent</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">pNode<span class="token punctuation">,</span>qNode</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token comment">// 层数相同</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>pNode<span class="token punctuation">.</span>depth<span class="token operator">===</span>qNode<span class="token punctuation">.</span>depth<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">// 一路往上找父节点</span>
            <span class="token keyword">let</span> p<span class="token operator">=</span>pNode
            <span class="token keyword">let</span> q<span class="token operator">=</span>qNode

            <span class="token keyword">while</span><span class="token punctuation">(</span>p<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token operator">!==</span>q<span class="token punctuation">.</span>node<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">{</span>
                p<span class="token operator">=</span>p<span class="token punctuation">.</span>parentNode
                q<span class="token operator">=</span>q<span class="token punctuation">.</span>parentNode
            <span class="token punctuation">}</span>

            <span class="token comment">// console.log(p)</span>

            <span class="token keyword">return</span> p
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">const</span> res<span class="token operator">=</span><span class="token function">getParent</span><span class="token punctuation">(</span>pNode<span class="token punctuation">,</span>qNode<span class="token punctuation">)</span>

    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span>

    <span class="token keyword">return</span> res<span class="token punctuation">.</span>node
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br><span class="line-number">97</span><br><span class="line-number">98</span><br><span class="line-number">99</span><br><span class="line-number">100</span><br><span class="line-number">101</span><br><span class="line-number">102</span><br><span class="line-number">103</span><br><span class="line-number">104</span><br><span class="line-number">105</span><br><span class="line-number">106</span><br><span class="line-number">107</span><br><span class="line-number">108</span><br><span class="line-number">109</span><br><span class="line-number">110</span><br></div></div><ul><li>优化版本</li></ul> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */</span>
<span class="token comment">/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">lowestCommonAncestor</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">root<span class="token punctuation">,</span> p<span class="token punctuation">,</span> q</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    
    <span class="token comment">// 使用map简化空间复杂度</span>
    <span class="token keyword">let</span> map<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Map</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token comment">// 使用标记数组存储节点 优化时间复杂度</span>
    <span class="token keyword">let</span> redNodes<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Set</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token comment">// 遍历树</span>
    map<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>val<span class="token punctuation">,</span><span class="token keyword">null</span><span class="token punctuation">)</span>
    <span class="token keyword">const</span> <span class="token function-variable function">travelTree</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">root</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>root<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> 
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">{</span>
            map<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>left<span class="token punctuation">.</span>val<span class="token punctuation">,</span>root<span class="token punctuation">)</span>
            <span class="token function">travelTree</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>left<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">{</span>
            map<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>right<span class="token punctuation">.</span>val<span class="token punctuation">,</span>root<span class="token punctuation">)</span>
            <span class="token function">travelTree</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>right<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token function">travelTree</span><span class="token punctuation">(</span>root<span class="token punctuation">)</span>

    <span class="token comment">// p 往上走，走到根，其中经过的节点全部加入redNodes数组</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>p<span class="token punctuation">.</span>val<span class="token operator">!==</span>root<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">{</span>
        redNodes<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>p<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
        p<span class="token operator">=</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>p<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>q<span class="token punctuation">.</span>val<span class="token operator">!==</span>root<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>redNodes<span class="token punctuation">.</span><span class="token function">has</span><span class="token punctuation">(</span>q<span class="token punctuation">.</span>val<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">break</span>
        <span class="token punctuation">}</span>
        q<span class="token operator">=</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>q<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> q
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br></div></div><h4 id="_684-冗余连接-模板题-用于找环的模板"><a href="#_684-冗余连接-模板题-用于找环的模板" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/redundant-connection/description/" target="_blank" rel="noopener noreferrer">684. 冗余连接(模板题)（用于找环的模板）<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>树可以看成是一个连通且 <strong>无环</strong> 的 <strong>无向</strong> 图。</p> <p>给定往一棵 <code>n</code> 个节点 (节点值 <code>1～n</code>) 的树中添加一条边后的图。添加的边的两个顶点包含在 <code>1</code> 到 <code>n</code> 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 <code>n</code> 的二维数组 <code>edges</code> ，<code>edges[i] = [ai, bi]</code> 表示图中在 <code>ai</code> 和 <code>bi</code> 之间存在一条边。</p> <p>请找出一条可以删去的边，删除后可使得剩余部分是一个有着 <code>n</code> 个节点的树。如果有多个答案，则返回数组 <code>edges</code> 中最后出现的边。</p> <p><strong>示例 1：</strong></p> <p><img src="https://pic.leetcode-cn.com/1626676174-hOEVUL-image.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://pic.leetcode-cn.com/1626676179-kGxcmu-image.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示:</strong></p> <ul><li><code>n == edges.length</code></li> <li><code>3 &lt;= n &lt;= 1000</code></li> <li><code>edges[i].length == 2</code></li> <li><code>1 &lt;= ai &lt; bi &lt;= edges.length</code></li> <li><code>ai != bi</code></li> <li><code>edges</code> 中无重复元素</li> <li>给定的图是连通的</li></ul> <h4 id="无向图找环"><a href="#无向图找环" class="header-anchor">#</a> ==无向图找环==</h4> <h5 id="解题思路-6"><a href="#解题思路-6" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 这条玩文字游戏，其实本质就是判断每加入一条边是否可以形成环
<span class="token number">2</span>. 如果形成了，把新加的边返回
<span class="token number">3</span>. 如何判断是否有环
	<span class="token number">1</span>. 双向图
	<span class="token number">2</span>. 递归出边
	<span class="token number">3</span>. 递归的出边可以是父亲，也可以是其他边
		递归父亲不算，如果其他边已经被访问过了，说明形成了环
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><h5 id="完整代码-5"><a href="#完整代码-5" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number[][]} edges
 * @return {number[]}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">findRedundantConnection</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">edges</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 问题的本质在于找环</span>

  <span class="token comment">// dfs找环</span>

  <span class="token comment">// 我们一条边一条边的加，看没加一条边是否会形成环，如果形成，则返回</span>

  <span class="token comment">// 定义一个出边数组</span>
  <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>edges<span class="token punctuation">.</span>length<span class="token punctuation">)</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> edges<span class="token punctuation">.</span>length <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// let newArr=new Array()</span>
    arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// dfs找环</span>
  <span class="token comment">// 定义一个visited数组</span>
  <span class="token keyword">let</span> visited <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>edges<span class="token punctuation">.</span>length <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token boolean">false</span><span class="token punctuation">)</span>
  <span class="token keyword">let</span> hasCycle <span class="token operator">=</span> <span class="token boolean">false</span>

  <span class="token keyword">const</span> <span class="token function-variable function">dfs</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token parameter">x<span class="token punctuation">,</span> father</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
    visited<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span>
    <span class="token comment">// 遍历出边，因为双向，所以可以出边指向父亲，执行父亲的不算</span>
    arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">item</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>item <span class="token operator">===</span> father<span class="token punctuation">)</span> <span class="token keyword">return</span>

      <span class="token keyword">if</span> <span class="token punctuation">(</span>visited<span class="token punctuation">[</span>item<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        hasCycle <span class="token operator">=</span> <span class="token boolean">true</span>
      <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token function">dfs</span><span class="token punctuation">(</span>item<span class="token punctuation">,</span> x<span class="token punctuation">)</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span><span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 遍历edges数组，双向加边</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> edges<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> source <span class="token operator">=</span> edges<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token keyword">let</span> target <span class="token operator">=</span> edges<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span>

    arr<span class="token punctuation">[</span>source<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span>
    arr<span class="token punctuation">[</span>target<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>source<span class="token punctuation">)</span>

    <span class="token comment">// 每加一条边，看是否存在环,父亲一开始没有(-1)</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> edges<span class="token punctuation">.</span>length <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span>
    <span class="token punctuation">}</span>
    <span class="token function">dfs</span><span class="token punctuation">(</span>source<span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>hasCycle<span class="token punctuation">)</span> <span class="token keyword">return</span> edges<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
  <span class="token punctuation">}</span>

  <span class="token keyword">return</span> <span class="token keyword">null</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br></div></div><h4 id="_207-课程表"><a href="#_207-课程表" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/course-schedule/description/" target="_blank" rel="noopener noreferrer">207. 课程表<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>你这个学期必须选修 <code>numCourses</code> 门课程，记为 <code>0</code> 到 <code>numCourses - 1</code> 。</p> <p>在选修某些课程之前需要一些先修课程。 先修课程按数组 <code>prerequisites</code> 给出，其中 <code>prerequisites[i] = [ai, bi]</code> ，表示如果要学习课程 <code>ai</code> 则 <strong>必须</strong> 先学习课程 <code>bi</code> 。</p> <ul><li>例如，先修课程对 <code>[0, 1]</code> 表示：想要学习课程 <code>0</code> ，你需要先完成课程 <code>1</code> 。</li></ul> <p>请你判断是否可能完成所有课程的学习？如果可以，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= numCourses &lt;= 105</code></li> <li><code>0 &lt;= prerequisites.length &lt;= 5000</code></li> <li><code>prerequisites[i].length == 2</code></li> <li><code>0 &lt;= ai, bi &lt; numCourses</code></li> <li><code>prerequisites[i]</code> 中的所有课程对 <strong>互不相同</strong></li></ul> <h4 id="解题方法"><a href="#解题方法" class="header-anchor">#</a> 解题方法</h4> <ul><li>dfs有向图找环</li> <li>bfs有向图找环</li></ul> <h5 id="dfs"><a href="#dfs" class="header-anchor">#</a> dfs</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 深度搜索，遇到没有访问过的节点就递归调用
<span class="token number">2</span>. 一路递归下去，在没有返回的情况下，如果发现某个节点的出边已经被访问，有环
<span class="token number">3</span>. 递归回头时，把该节点已经访问设为false（防止假环）
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">canFinish</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">numCourses<span class="token punctuation">,</span> prerequisites</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 课程表，判断能否修完所有课程的标准为</span>
    <span class="token comment">// 不形成环 ==&gt;可以</span>
    <span class="token comment">// 形成环==&gt; 不可以</span>

    <span class="token comment">// 深度优先搜索看是否形成了环</span>

   

    <span class="token comment">// 定义出边数组</span>
    <span class="token keyword">let</span> arr<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>numCourses<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 根据课程表加边</span>
    <span class="token keyword">let</span> hasCycle<span class="token operator">=</span><span class="token boolean">false</span>
    <span class="token keyword">let</span> visited<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token boolean">false</span><span class="token punctuation">)</span>

     <span class="token keyword">const</span> <span class="token function-variable function">dfs</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">x</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        visited<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>
        <span class="token comment">// x的出边</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>visited<span class="token punctuation">[</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                hasCycle<span class="token operator">=</span><span class="token boolean">true</span>
                <span class="token keyword">break</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span><span class="token punctuation">{</span>
                <span class="token function">dfs</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        visited<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">false</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>prerequisites<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> target<span class="token operator">=</span>prerequisites<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
        <span class="token keyword">let</span> source<span class="token operator">=</span>prerequisites<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>visited<span class="token punctuation">.</span>length<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            visited<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">false</span>
        <span class="token punctuation">}</span>

        arr<span class="token punctuation">[</span>source<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span>

        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>source<span class="token punctuation">)</span>

        <span class="token function">dfs</span><span class="token punctuation">(</span>source<span class="token punctuation">)</span>

        <span class="token comment">// 判断是否形成环</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>hasCycle<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token boolean">false</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> <span class="token boolean">true</span>

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br></div></div><h5 id="bfs-找环法"><a href="#bfs-找环法" class="header-anchor">#</a> bfs 找环法</h5> <p>有向图的一些概念</p> <ul><li>出度：该节点指向其他节点的边的数量</li> <li>入度：其他节点指向该节点的边的数量</li></ul> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 找环方法
	找到入度为0的节点，访问
	它可能指向了其他节点，被指向的节点入度-1
	
	循环上述操作，如果所有节点都被访问了，说明没有环
	否则有环
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">canFinish</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">numCourses<span class="token punctuation">,</span> prerequisites</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 使用bfs找环</span>

    <span class="token comment">// 判断入度为0的点开始学习</span>

    <span class="token comment">// 直到没有入度为0的节点，这时候看看已经访问过的节点是否等于课程数</span>

    <span class="token comment">// 定义出边数组</span>
    <span class="token keyword">let</span> arr<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span>

    <span class="token comment">// 定义入度数组，记录每个节点的入度</span>
    <span class="token keyword">let</span> inDeg<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>numCourses<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>numCourses<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">const</span> <span class="token function-variable function">tpSort</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>

        <span class="token comment">// 找到入度为0的节点</span>

        <span class="token keyword">let</span> queue<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
        <span class="token keyword">let</span> cnt<span class="token operator">=</span><span class="token number">0</span>

        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>inDeg<span class="token punctuation">)</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>inDeg<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>inDeg<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">===</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">while</span><span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">// console.log('queue')</span>
            <span class="token keyword">let</span> x<span class="token operator">=</span>queue<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
            queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
            cnt<span class="token operator">++</span>

            <span class="token comment">// 解放这个节点，其出边的节点入度-1</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                inDeg<span class="token punctuation">[</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">--</span>

                <span class="token keyword">if</span><span class="token punctuation">(</span>inDeg<span class="token punctuation">[</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">===</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                    queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>

        <span class="token punctuation">}</span>
        <span class="token comment">// console.log(cnt)</span>

        <span class="token keyword">return</span> cnt
    <span class="token punctuation">}</span>

    <span class="token comment">// 加边</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>prerequisites<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> target<span class="token operator">=</span>prerequisites<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
        <span class="token keyword">let</span> source<span class="token operator">=</span>prerequisites<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span>

        arr<span class="token punctuation">[</span>source<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>target<span class="token punctuation">)</span>
        inDeg<span class="token punctuation">[</span>target<span class="token punctuation">]</span><span class="token operator">++</span>

        <span class="token comment">// 开始拓扑排序，也即bfs找环</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token function">tpSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">return</span> res<span class="token operator">===</span>numCourses
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br></div></div></div></div>  <div class="page-edit"><div class="edit-link"><a href="https://github.com/linxin1123/vuepress-blog/edit/master/docs/07.算法/41.算法训练营/09.树与图-cnblog.md" target="_blank" rel="noopener noreferrer">编辑</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">2023/02/17, 11:29:32</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/1a456e/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">三分-二分答案</div></a> <a href="/pages/7c3255/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">二叉搜索树</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/1a456e/" class="prev">三分-二分答案</a></span> <span class="next"><a href="/pages/7c3255/">二叉搜索树</a>→
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/0b785d/"><div>
            Vuex
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/c59cc0/"><div>
            Vue响应式原理
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/83cc7a/"><div>
            Vue虚拟DOM-cnblog
            <!----></div></a> <span class="date">03-14</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div></main></div> <div class="footer"><div class="icons"><a href="3010733382@qq.com" title="发邮件" target="_blank" class="iconfont icon-youjian"></a><a href="https://github.com/linxin1123" title="GitHub" target="_blank" class="iconfont icon-github"></a><a href="https://music.163.com/#/playlist?id=755597173" title="听音乐" target="_blank" class="iconfont icon-erji"></a></div> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2022-2023
    <span>lingxin | <a href="https://github.com/linxin1123/vuepress-blog/blob/master/LICENSE" target="_blank">MIT License</a></span></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div> <div title="主题模式" class="button blur theme-mode-but iconfont icon-zhuti"><ul class="select-box" style="display:none;"><li class="iconfont icon-zidong">
          跟随系统
        </li><li class="iconfont icon-rijianmoshi">
          浅色模式
        </li><li class="iconfont icon-yejianmoshi">
          深色模式
        </li><li class="iconfont icon-yuedu">
          阅读模式
        </li></ul></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div></div></div>
    <script src="/assets/js/app.57550e13.js" defer></script><script src="/assets/js/2.f014c35f.js" defer></script><script src="/assets/js/107.a81b32d7.js" defer></script>
  </body>
</html>
